#ifndef __SLOWALLPAIRSSHORTESTPATH__
#define __SLOWALLPAIRSSHORTESTPATH__
#define MAX 100
#define MAXINT std::numeric_limits<int>::max()
#include <limits>
#include <algorithm>
#include <iostream>
#include <iomanip>

int weight[MAX][MAX];
int shortest[MAX][MAX];

//let the path extend with an edge
void ExtendShortestPath(int weight[][MAX], int shortest[][MAX], int n){
	for(int i = 0; i < n; ++i)
		for(int j = 0 ; j < n; ++j)
			for(int k = 0; k < n; ++k)
				if(i != j && shortest[i][k] != MAXINT && weight[k][j] != MAXINT){
					int temp = shortest[i][k] + weight[k][j];
					if(shortest[i][j] > temp)
						shortest[i][j] = temp;
				}
}

void ShowResult(int);
//the number of the edges is less than n 
//extend the path(initialize with weight) with one weight each time
//n-2 times (from 1 to n-1)
void SlowAllPairsShortestPath(int weight[][MAX], int n){
	for(int i = 0 ; i < n; ++i)
		for(int j = 0 ; j < n; ++j)
			shortest[i][j] = weight[i][j];
	for(int i = 1; i < n; ++i)
		ExtendShortestPath(weight, shortest, n);
	ShowResult(n);
}
//extend the path with 2^n weight each time
//lgn times
void FasterPairShortestPath(int weight[][MAX], int n){
	for(int i = 0; i < n ; ++i)
		for(int j = 0; j < n ; ++j)
			shortest[i][j] = weight[i][j];
	int i = 1;
	for(;;){
		if(i >= n-1) break;
		ExtendShortestPath(shortest, shortest, n);
		i *= 2;
	}
	ShowResult(n);
}

void ShowResult(int n){
	for(int i = 0 ;i < n ; ++i){
		for(int j = 0 ; j < n; ++j)
			std::cout <<std::setw(3)<< shortest[i][j] <<" ";
		std::cout << std::endl;
	}
}

void TestDrive(){
	for(int i = 0; i < 5; ++i)
		for(int j = 0; j < 5; ++j){
			if(i != j)
				weight[i][j] = MAXINT;
			else
				weight[i][j] = 0;
		}

	weight[0][1] = 3; weight[0][2] = 8; weight[0][4] = -4;
	weight[1][4] = 7; weight[1][3] = 1;
	weight[2][1] = 4;
	weight[3][2] = -5; weight[3][0] = 2;
	weight[4][3] = 6;

	FasterPairShortestPath(weight, 5);

}
#endif